package com.yan_jiu_sheng.LeetCodeHot100;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode.cn/problems/palindrome-partitioning/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考通过
 *
 * @author yulongtian
 * @create 2024-07-29 13:17
 */
public class Test94 {
    public static void main(String[] args) {

    }

    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<List<String>>();
        List<String> path = new ArrayList<>();
        dfs(0, s, ans, path);
        return ans;
    }

    private void dfs(int i, String s, List<List<String>> ans, List<String> path) {
        if (i == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int j = i; j < s.length(); j++) {
            String t = s.substring(i, j + 1);
            if (checkBack(t)) {
                path.add(t);
                dfs(j + 1, s, ans, path);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean checkBack(String t) {
        int left = 0;
        int right = t.length() - 1;
        while (left < right) {
            if (t.charAt(left) == t.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }

}
